package com.java.comprehensive.arithmetic.leecode.medium;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 窦绍飞
 * @Date: 2022/8/5
 */
public class LeetCode_131 {

	List<List<String>> result = new ArrayList<>();
	List<String> temp = new ArrayList<>();

	public List<List<String>> partition(String s) {

		if (s.length() < 1) return result;
		backtracking(s, 0);
		return result;
	}

	public void backtracking(String s, int startIndex) {
		if (startIndex >= s.length()) {
			result.add(new ArrayList<>(temp));
			return;
		}
		for (int i = startIndex; i < s.length(); i++) {
			if (isPalindrome(s, startIndex, i + 1)) {
				temp.add(s.substring(startIndex, i + 1));
			} else {
				continue;
			}
			backtracking(s, i + 1);
			temp.remove(temp.size() - 1);
		}
	}

	private boolean isPalindrome(String palindrome, int l, int r) {
		return palindrome.substring(l, r).length() > 0 && palindrome.substring(l, r).equals(new StringBuilder(palindrome.substring(l, r)).reverse().toString());
	}

	public static void main(String[] args) {
		String s = "aab";
		LeetCode_131 leetCode_131 = new LeetCode_131();
		System.out.println(leetCode_131.partition(s));
	}
}
